#include "BinaryTree.h"

BTNode* BuyNode(BTDataType x)
{
    BTNode* tmp=(BTNode*)malloc(sizeof(BTNode));
    if(tmp==NULL)
    {
        perror("malloc fail");
        return 0;
    }
    tmp->data=x;
    tmp->left=NULL;
    tmp->right=NULL;
    return tmp;
}

BTNode* CreatBinaryTree()
{
    BTNode* node1 = BuyNode(1);
    BTNode* node2 = BuyNode(2);
    BTNode* node3 = BuyNode(3);
    BTNode* node4 = BuyNode(4);
    BTNode* node5 = BuyNode(5);
    BTNode* node6 = BuyNode(6);
    BTNode* node7 = BuyNode(7);
    
    node1->left=node2;
    node1->right=node4;
    node4->left=node5;
    node2->left=node3;
    node4->right=node6;
    node3->right=node7;

    return node1;
}

void PreOrder(BTNode* root)
{
    if(root==NULL)
    {
        printf("NULL ");
        return;
    }
    printf("%d ",root->data);
    PreOrder(root->left);
    PreOrder(root->right);
}

void InOrder(BTNode* root)
{
    if(root==NULL)
    {
        printf("NULL ");
        return ;
    }
    InOrder(root->left);
    printf("%d ",root->data);
    InOrder(root->right);
}

void PostOrder(BTNode* root)
{
    if(root==NULL)
    {
        printf("NULL ");
        return ;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%d ",root->data);
}

int BinaryTreeSize(BTNode* root)
{
    if(root==NULL)
    {
        return 0;
    }
    return BinaryTreeSize(root->left)
        +BinaryTreeSize(root->right)+1;
}

int BTreeHeight(BTNode* root)
{
    if(root==NULL)
    {
        return 0; 
    }
    int left=BTreeHeight(root->left);
    int right=BTreeHeight(root->right);
    return left>right?(left+1):(right+1);
}

int BinaryTreeLeafSize(BTNode* root)
{
    if(root==NULL)
    {
        return 0;
    }
    if(root->left == NULL && root->right == NULL)
    {
        return 1;
    }
   return  BinaryTreeLeafSize(root->left)
        +BinaryTreeLeafSize(root->right);
}

int BinarySizeLevelKSize(BTNode* root,int k)
{
    assert(k>0);
    if(root==NULL)
    {
        return 0;
    }
    if(k==1)
    {
        return 1;
    }
    return BinarySizeLevelKSize(root->left,k-1)
        +BinarySizeLevelKSize(root->right,k-1);
}

//BTNode* BinaryTreeFind(BTNode* root,BTDataType x)
//{
   //     if(root==NULL)
   //     {
   //         return NULL;
   //     }
   //     if(root->data==x)
   //     {
   //         return root;
   //     }
//}
